package leetcode.code0093;

import java.util.ArrayList;
import java.util.List;

public class Solution extends Solution93 {
	List<String> ans;
	int LEN;
	int LEN0;
	int LEN1;
	int LEN2;

	@Override
	public List<String> restoreIpAddresses(String s) {
		char[] chars = s.toCharArray();
		LEN = s.length();
		LEN0 = LEN - 4;// 第一个点能达到的最大索引
		LEN1 = LEN - 3;// 第二个
		LEN2 = LEN - 2;// 第三个
		ans = new ArrayList<>();
		this.f(chars, 0, 0, new int[3]);// chars数组，从index位置后，加入了几个点
		return ans;
	}

	// 从index开始，已经加入dot个点，dots记录每个点在chars上的位置
	private void f(char[] chars, int index, int dot, int[] dots) {
		if (dot == 3) {
			if (check(chars, dots[2] + 1, LEN - dots[2] - 1)) {// 检查最后一个数
				StringBuffer sb = new StringBuffer();
				sb.append(chars, 0, dots[0] + 1).append('.');
				sb.append(chars, dots[0] + 1, dots[1] - dots[0]).append('.');
				sb.append(chars, dots[1] + 1, dots[2] - dots[1]).append('.');
				sb.append(chars, dots[2] + 1, LEN - dots[2] - 1);
				ans.add(sb.toString());
			}
			return;
		}
		int range = Math.min(range(dot), index + 2);// 这个点能达到的最大距离
		int num = 0;
		int count = 0;
		for (int i = index; i <= range; i++) {
			char c = chars[i];
			num = num * 10 + c - '0';
			count++;
			dots[dot] = i;
			if ((count == 1 && num < 10) // 一位数
					|| (count == 2 && num > 9 && num < 100)// 两位数
					|| (count == 3 && num > 99 && num < 256// 三位数
					)) {
				this.f(chars, i + 1, dot + 1, dots);
			}
		}
	}

	private boolean check(char[] chars, int index, int size) {
		if (size > 3 || (chars[index] == '0' && size != 1)) {// 超过三个不行，第一个是0，不是1个不行
			return false;
		}
		int num = 0;
		for (int i = index; i < index + size; i++) {
			num = num * 10 + chars[i] - '0';
		}
		return num >= 0 && num <= 255;
	}

	private int range(int dot) {
		if (dot == 0) {
			return LEN0;
		}
		if (dot == 1) {
			return LEN1;
		}
		return LEN2;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
//		String s = "1111";
//		char[] c = s.toCharArray();
//		int[] dot = new int[3];
//		dot[0] = 0;
//		dot[1] = 1;
//		dot[2] = 2;
//		StringBuffer sb = new StringBuffer();
//		sb.append(c, 0, dot[0] + 1).append('.');
//		sb.append(c, dot[0] + 1, dot[1] - dot[0]).append('.');
//		sb.append(c, dot[1] + 1, dot[2] - dot[1]).append('.');
//		sb.append(c, dot[2] + 1, s.length() - dot[2] - 1);
//		System.out.println(sb.toString());
	}

}
